﻿// Copyright 2023 Maintainers of NUKE.
// Distributed under the MIT License.
// https://github.com/nuke-build/nuke/blob/master/LICENSE

using System;
using System.Collections.Generic;
using System.Linq;

namespace Nuke.Common.Utilities.Collections;

public static partial class EnumerableExtensions
{
    public static IEnumerable<T> TSort<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false)
    {
        var sorted = new List<T>();
        var visited = new HashSet<T>();

        foreach (var item in source)
            Visit(item, visited, sorted, dependencies, throwOnCycle);

        return sorted;
    }

    private static void Visit<T>(T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle)
    {
        if (visited.Contains(item))
        {
            if (throwOnCycle && !sorted.Contains(item))
                throw new Exception($"Cyclic dependency found involving {item}.");

            return;
        }

        visited.Add(item);

        foreach (var dep in dependencies(item))
            Visit(dep, visited, sorted, dependencies, throwOnCycle);

        sorted.Add(item);
    }
}
